public class code2 {
    // 牛客 top101 括号生成

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // 同样的，这道题也用到的是递归的思想，思路如下：
        // 因为是要产生 n 组 ()
        // 我们可以通过 递归的方式实现 n 个 (
        // 在通过递归的方式实现 n 个 )

        // 首先定义出一个 顺序表用来存储返回值
        ArrayList<String> list = new ArrayList<>();

        String str = new String();

        // 实现一个方法来进行创建添加
        add(0, 0, list, n, str);
        return list;
    }

    // 这里要设定的参数包含：
    // 左括号数量记录 left，右括号数量记录 right，返回值顺序表 list，总参数 n
    private void add(int left, int right, ArrayList<String> list, int n, String str){
        // 首先先设定一个判断终止条件
        if(left == n && right == n) {
            list.add(str);
            return;
        }

        if(left < n) {
            // 此时只要左侧 ( 小于 n 就需要针对字符串进行拼接
            add(left + 1, right, list, n, str + '(');
        }

        if(right < n && left > right) {
            // 同样的这里也要针对右括号进行判断
            add(left, right + 1, list, n, str + ')');
        }
    }
}
